﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BackPack
{
	/*
	 * 动态规划思想：
	 *  在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。
	 * 
	 * 二：使用规则
    现在我们知道动态规划要解决啥问题了，那么什么情况下我们该使用动态规划呢？
   ①  最优化原理（最优子结构性质）：
           如果一个问题的最优策略它的子问题的策略也是最优的，则称该问题具有“最优子结构性质”。
   ②  无后效性：
           当一个问题被划分为多个决策阶段，那么前一个阶段的策略不会受到后一个阶段所做出策略的影响。
   ③  子问题的重叠性：
          这个性质揭露了动态规划的本质，解决冗余问题，重复的子问题我们可以记录下来供后阶段决策时直接使用，从而降低算法复杂度。

三：求解步骤
      ①   描述最优解模型。
      ②   递归的定义最优解，也就是构造动态规划方程。
      ③   自底向上的计算最优解。
      ④   最后根据计算的最优值得出问题的最佳策略。

四：与其他算法的差异
     ① 递归：  递归采用的是“由上而下”的解题策略并带有可能的”子问题“重复调用，时间复杂度自然高。而”动态规划“采用”自下而上“并带有临时存储器保存上一策略的最优解，空间换时间。
     ② 分治：  同样两者都是将问题划分为很多的子问题，不同的是”动态规划“中各子问题是相互联系的。
     ③ 贪心：  要注意的是贪心算法每走一步都是不可撤回的，而动态规划是在一个问题的多种策略中寻找最优策略，所以动态规划中前一种策略可能会被后一种策略推翻。
	 */
	class Program
	{
		/*
		 * 五：举例
				动态规划中，最经典最著名的例子莫过于”背包问题“，现有：
				苹果： 1kg    12￥
				梨子： 1kg     3￥
				葡萄： 1kg    10￥
				板栗： 1kg    25￥  
				现有一个背包，只能装3kg水果，那么如何得到物品价值最大化？
		 */
		static void Main(string[] args)
		{
			Goods goods = new Goods()
			{
				LimitWeight = 3,
				LimitNum = 4,
				Weight = new double[4] { 1, 1, 1, 1 },
				Value = new double[4] { 12, 3, 10, 25 }
			};

			BackPack(goods, 0, 0, goods.Value.Sum());
			Console.WriteLine("经过最优化求解：\n");
			for (int i = 0; i < goods.Selected.Length; i++)
			{
				if (goods.Selected[i])
				{
					Console.WriteLine("重量：" + goods.Weight[i] + " 价值：" + goods.Value[i]);
				}
			}
			Console.Read();
		}

		static double maxValue;
		static bool[] selected = new bool[4];
		static void BackPack(Goods good, int i, double tw, double tv)
		{
			//当前追加物品的重量
			var currentWeight = tw + good.Weight[i];
			//当前重量小于限制重量则继续追加
			if (currentWeight <= good.LimitWeight)
			{
				selected[i] = true;
				//如果当前不是最后一个商品，则继续追加
				if (i < good.LimitNum - 1)
				{
					BackPack(good, i + 1, tw + good.Weight[i], tv);
				}
				else
				{
					for (int k = 0; k < good.LimitNum; k++)
					{
						good.Selected[k] = selected[k];
					}
					maxValue = tv;
				}
			}

			selected[i] = false;
			//这里就体现了动态规划的根本目的，解决冗余
			if (tv - good.Value[i] > maxValue)
			{
				if (i < good.LimitNum - 1)
				{
					//排除当前物品所剩余的价值总值
					var exceptNotSelectedValue = tv - good.Value[i];
					BackPack(good, i + 1, tw, exceptNotSelectedValue);
				}
				else
				{
					for (int k = 0; k < good.LimitNum; k++)
					{
						good.Selected[k] = selected[k];
					}
					maxValue = tv - good.Value[i];
				}
			}
		}
	}

	#region 商品的实体
	/// <summary>
	/// 商品的实体
	/// </summary>
	public class Goods
	{
		public double[] Value = new double[4];
		public double[] Weight = new double[4];
		public bool[] Selected = new bool[4];
		public int LimitNum { get; set; }
		public double LimitWeight { get; set; }
	}
	#endregion
}
